//class Solution {
//public:
//    TreeNode* sortedArrayToBST(vector<int>& nums) {
//        return dfs(nums, 0, nums.size() - 1);
//    }
//    TreeNode* dfs(vector<int>& nums, int left, int right)
//    {
//        if (left > right) return nullptr;
//        int mid = (left + right) >> 1;
//        TreeNode* node = new TreeNode(nums[mid]);
//        node->left = dfs(nums, left, mid - 1);
//        node->right = dfs(nums, mid + 1, right);
//        return node;
//    }
//};



class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* lessNewHead = new ListNode, * lessPrev = lessNewHead;
        ListNode* greaterNewHead = new ListNode, * greaterPrev = greaterNewHead;
        ListNode* cur = head;
        while (cur)
        {
            if (cur->val < x)
            {
                lessPrev->next = cur;
                lessPrev = lessPrev->next;
            }
            else
            {
                greaterPrev->next = cur;
                greaterPrev = greaterPrev->next;
            }
            cur = cur->next;
        }
        lessPrev->next = greaterNewHead->next;
        greaterPrev->next = nullptr;

        lessPrev = lessNewHead->next;
        delete lessNewHead;
        delete greaterNewHead;
        return lessPrev;
    }
};